package 图;
import java.util.Arrays;
import java.util.PriorityQueue;
public class leetcode2039网络空闲 {
	//   直接 看数据 范围 就行 了
	static int head [] = new int[101];
	static Edge edges [] = new Edge[6001];
	
	/**
	 * 这里 还有 一些 小的 细节 在这   里 面  
	 * 这里的 细节 就是  java  基础 语法 的  一些 细节了
	 * static 声明的 属性 变量的 生存 周期 的 问题 ( 全局 共享的 )
	 * 如果 这里    对 index  变量 使用 static 进行  修饰的  话  在 leetcode  上面 会 报错的
	 */
	/**
	 * 很难 不说秒啊 说是实话 
	 *  还是 遵循 那个 原则  static 只能调用    被  static
	 *   修饰的 变量 和 方法  
	 *   通过 这里 明白 那些 应该 用static 修饰 那些 不用 更加合理 吧
	 */
	static {
		for(int  i = 0;i < 6001;i++) {
			edges[i] = new Edge();
		}
	}
//	static int index ;
	int index ;
	static int INF = Integer.MAX_VALUE;
	 int solution(int martix[][],int n,int k) {
		int len = martix.length;
//		int head [] = new int [n + 1];
//		Edge edges[] = new Edge[len + 1];
//		  等一下 把这个  直接    写在 静态 代码   块 里面
//		 这还有 一个 细节 在这里   因为 是 有 向图 所以 直接   建图 和 建边 写在 一起 
		Arrays.fill(head, -1);
		for(int i = 0;i < len;i++) {
//			edges[i] = new Edge();
			add(martix[i][0],martix[i][1],martix[i][2]);
		}
//		System.out.println(Arrays.toString(head));
		int dis [] = new int [n + 1];
		Arrays.fill(dis, INF);
		dis[k] = 0;
		boolean vis [] = new boolean [n + 1];
		PriorityQueue<int []> queue = new PriorityQueue<>((o1,o2) -> (o1[1] - o2[1]));
		queue.add(new int [] {k,0});
		while(!queue.isEmpty()) {
			int cur [] = queue.poll();
			if(vis[cur[0]]) 
				continue;
			// 下面  是  更新  邻接点 
			for(int edgeIndex = head[cur[0]] ;edgeIndex != -1 ;edgeIndex = edges[edgeIndex].next) {
				int to = edges[edgeIndex].to;
				int w = edges[edgeIndex].weight;
				if(dis[to] > dis[cur[0]] + w) {
					dis[to] = dis[cur[0]] + w;
					queue.offer(new int[] {to,dis[to]});
				}
			}
			vis[cur[0]] = true;
		}
//		System.out.println(Arrays.toString(dis));
		int ans = 0;
		for(int  i = 1;i <= n;i++ ) {
			if(dis[i] == INF) {
				return - 1;
			}
			if(ans <= dis[i]) {
				ans = dis[i];
			}
		}
		return ans;
	}
     void add(int from,int to,int weight ) { 
		edges[index].to = to;
		edges[index].weight = weight;
		edges[index].next = head[from];
		head[from] = index++;
	}
	
	static class Edge {
		int to;
		int weight;
		int next  = -1;
	}
	public static void main(String []args) {
		int [][]martix = {{2,1,1},{2,3,1},{3,4,1}};
		int  n = 4, k = 2;
		leetcode2039网络空闲 test = new leetcode2039网络空闲();
		System.out.println(test.solution(martix,n,k));
		System.out.println(test.index);
		/**
		 * 在执行   一遍 这个 solution  就会 报 空指针的 异常   原因 在于 
		 * 将  全局       变量  index  static  化造成的 错误   
		 * 
		 */
		leetcode2039网络空闲 test1 = new leetcode2039网络空闲();
		System.out.println(test.solution(martix,n,k));
		System.out.println(test.index);
	}
}